package press.xiang.utils;

import easyopt.common.EasyMath;

import java.util.Arrays;

/**
 * 禁忌算法
 * @author xiang
 * @version 1.0
 * @description: TODO
 * @date 2022/4/22 5:23 下午
 */
public class TabuUtils {

    /***
     * @description: 根据输入的参数，使用禁忌搜索算法，获取该TSP问题距离最短路径
     * @param dist 两点之间，距离二维矩阵，行和列必须相等
     * @param tabuLength 禁忌长度，正整数，一般可能在3-5之间
     * @param optNum 每次迭代保留的最好邻域个数
     * @return: int[] 返回一个路线
     * @author xiang
     * @date: 2022/4/21 2:48 下午
     */
    public static int[] optTspByTabu(double[][] dist,int tabuLength,int optNum){
        int cityQty = dist.length;
        int[] xnow = new int[cityQty];
        for (int i = 0; i < cityQty; i++) {
            xnow[i] = i;
        }
        // initialize Tabu Table
        int[][] tabuTable = new int[cityQty][cityQty];
        // 定义最优解及其目标函数值的变量并赋值
        int[] xbest = new int[cityQty];
        xbest = Arrays.copyOf(xnow,cityQty);
        double fbest = getTspDist(dist,xbest);

        int noGoodLoops = 0;

        boolean notEnd = true;
        while (notEnd) {
            // step3: create the neighborhood for the present solution- [2-opt]
            int[][] opt2 = EasyMath.combin2(cityQty - 1);
            int rows = opt2.length;
            int[][] cumbSolutions = new int[rows][cityQty];
            for (int i = 0; i < rows; i++) {
                cumbSolutions[i] = Arrays.copyOf(xnow, cityQty);
                int changePos1 = opt2[i][0] + 1;
                int changePos2 = opt2[i][1] + 1;
                cumbSolutions[i][changePos1] = xnow[changePos2];
                cumbSolutions[i][changePos2] = xnow[changePos1];
            }
            // 第一列是序号，第二列具体路径距离
            double[][] allDists = new double[rows][2];
            for (int i = 0; i < rows; i++) {
                allDists[i][1] = getTspDist(dist, cumbSolutions[i]);
                allDists[i][0] = i;
            }
            EasyMath.sortArray(allDists, new int[]{1});
            // 确定更新的解,并更新禁忌表，
            // 如果当前邻域解中最好的解的目标函数比fbest好，则直接选择排序后的邻域接的第一个解作为新的迭代起点
            // 如果全部领域接中最好的解的目标函数比fbest差，则从排序后领域的optNum后找出第一个没出于禁忌状态作为新的起点

            double nowFbest = allDists[0][1];
            // 新解迭代的城市编号
            int[] changeCityIdx = new int[2];
            if (nowFbest < fbest) {
                xnow = cumbSolutions[(int) allDists[0][0]];
                int nowSoluIdx = (int) allDists[0][0];
                changeCityIdx[0] = xnow[opt2[nowSoluIdx][0]];
                changeCityIdx[1] = xnow[opt2[nowSoluIdx][1]];

                // 更新全局解和最优解
                fbest = nowFbest;
                xbest = cumbSolutions[(int) allDists[0][0]];
                noGoodLoops = 0;
            } else {
                noGoodLoops++;
                for (int i = 0; i < optNum; i++) {
                    int nowSoluIdx = (int) allDists[i][0];
                    int cityId1 = xnow[opt2[nowSoluIdx][0]];
                    int cityId2 = xnow[opt2[nowSoluIdx][1]];
                    if (tabuTable[cityId1][cityId2] == 0) {
                        // 非禁忌状态可以互换
                        xnow = cumbSolutions[nowSoluIdx];
                        changeCityIdx[0] = cityId1;
                        changeCityIdx[1] = cityId2;
                        break;
                    }
                }
            }

            // 更新禁忌表
            for (int i = 0; i < cityQty; i++) {
                for (int j = 0; j < cityQty; j++) {
                    if (tabuTable[i][j] > 0) {
                        tabuTable[i][j]--;
                    }
                }
            }
            tabuTable[changeCityIdx[0]][changeCityIdx[1]] = tabuLength;
            tabuTable[changeCityIdx[1]][changeCityIdx[0]] = tabuLength;
            // step4: update the best solution and whether algorithm is terminated
            // 连续50代最优解没有更新结束
            if (noGoodLoops > 50) {
                notEnd = false;
            }
        }
        System.out.println(" the tabu route: "+Arrays.toString(xbest));
        System.out.println(" the minimal distance: "+fbest);
        return xbest;

    }



    /**
     * @description: 根据输入的仓库之间距离和调配路线，获取该路线的总长度
     * @param: dist 仓库之间的二维矩阵，行和列必须相等
     * @Param: route 调配路线经过各个仓库节点的孙旭，从0开始编号，0为起点和重点，必须为 route 的每一个值，后续的值不能相同
     * @return: double  返回总路程的长度，从节点0出发后每个仓库经过一次后返回节点0所需要的路径总长度
     * @author xiang
     * @date: 2022/4/21 9:11 上午
     */
    public static double getTspDist(double[][] dist,int[] route){
        double sumDist = 0;
        for (int i = 0; i < route.length -1; i++) {
            sumDist += dist[route[i]][route[i+1]];
        }
        sumDist+=dist[route[route.length-1]][route[0]];
        return sumDist;
    }
}
